public class Test39 {
    //解法一
    public static int treeDepth(TreeNode root){
        if (root == null) return 0;
        int left = treeDepth(root.left);
        int right = treeDepth(root.right);
        return left> right?(left+1) :(right+1);
    }

    public static  boolean isBalanced(TreeNode root){
        if (root == null) return true;
        int left = treeDepth(root.left);
        int rigth = treeDepth(root.right);
        int diff = left - rigth;
        if (diff > 1 ||diff < -1)return false;
        return isBalanced(root.left) && isBalanced(root.right);
    }
    /*
    用后序遍历的方式遍历二叉树的每一个结点，在遍历到一个结点之前我们就已经遍历了它的左右子树。
    只要在遍历每个结点的时候记录它的深度（某一结点的深度等于它到叶节点的路径的长度），
    我们就可以一边遍历一边判断每个结点是不是平衡的。
     */
    //解法二
    public static boolean isBalanced2(TreeNode root){
        int[] depth = new int[1];
        return isBalancedHelper(root,depth);
    }
    public static boolean isBalancedHelper(TreeNode root,int[] depth){
        if (root == null){//如果为空，则返回true
            depth[0] = 0;
            return true;
        }
        int[] left = new int[1];//记录左子树的深度
        int[] right = new int[1];//记录右子树的深度

        if (isBalancedHelper(root.left,left) && isBalancedHelper(root.right,right)){//如果是平衡树
            int diff = left[0] - right[0];//计算深度
            if (diff >= -1 && diff <= 1){//如果当前位置也是平衡树
                depth[0] = 1+(left[0] > right[0]? left[0] : right[0]);
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode();
        root.val = 1;
        root.left = new TreeNode();
        root.left.val = 2;
        root.right = new TreeNode();
        root.right.val = 3;
        root.left.left = new TreeNode();
        root.left.left.val = 4;
        root.left.right = new TreeNode();
        root.left.right.val = 5;
        root.right.left = new TreeNode();
        root.right.left.val = 6;
        root.right.right = new TreeNode();
        root.right.right.val = 7;

        System.out.println(treeDepth(root));
        System.out.println(isBalanced(root));

        System.out.println(isBalanced2(root));

        System.out.println("-----------------------");

        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(1);
        TreeNode n3 = new TreeNode(1);
        TreeNode n4 = new TreeNode(1);
        TreeNode n5 = new TreeNode(1);
        TreeNode n6 = new TreeNode(1);
        TreeNode n7 = new TreeNode(1);

        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n5.left = n7;

        System.out.println(isBalanced(n1));
        System.out.println(isBalanced2(n1));
        System.out.println("----------------");

    }
}
